/**
 * BinarySearch: 二分查找
 * 每次确认一半的数据样本， 所以是O(logN)复杂度
 */
public class BinarySearch {

    private BinarySearch() {}

    // 0, 1, 2, 3, 4, 5, 6, 7, 8, 9
    //                |
    // [lo, hi) 获得上边界
    // 0, 1, 2, 3, 4, 5, 6, 7, 8, 9
    //             |
    // [lo, hi] 获得下边界, 一半来说，上边界和下边界都可以，虽然惯用[lo, hi)，但是在二分
    // 查找中， 使用[lo, hi] 更方便一些， 不同意越界.
    public static <E extends Comparable<E>> int search(E[] elems, E key) {
        return search(elems, key, 0, elems.length - 1);
    }

    // 二分查找 - 循环
    public static <E extends Comparable<E>> int search(E[] elems, E key, int lo, int hi) {
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if (elems[mid].compareTo(key) == 0) {
                return mid;
            }else if (elems[mid].compareTo(key) < 0) {
                lo = mid + 1;
            }else {
                hi = mid - 1;
            }
        }
        return -1;
    }

    // 二分查找 - 递归
    public static <E extends Comparable<E>> int searchR(E[] elems, E key, int lo, int hi) {
        if (lo > hi) { return -1; }
        int mid = lo + (hi - lo) / 2;
        if (elems[mid].compareTo(key) < 0)  // 结果可能在右半边
            return searchR(elems, key, mid + 1, hi);
        if (elems[mid].compareTo(key) > 0)  // 结果可能在左半边
            return searchR(elems, key, lo, mid - 1);
        return mid;
    }
}
